題目

題目翻譯

給定一個字串 s ，給定 n 個字 word，找出所有子字串的開始下標，使得子字串包含了給定的所有單詞，順序可以不對應。如果有重複的單字，例如有 [ " foo " , " foo " ] 那麼子字串也必須含有兩個 " foo "，也就是說個數必須相同。

解題思路

這題是經典的「字串搜尋」問題，需要找到所有由單詞列表中的詞組成的子串的位置。每個子串必須由給定的單詞列表 words 中的每個詞拼接而成，且每個詞只能使用一次，順序無關。這樣的子串必須緊密相連並且不包含其他字符。

思路：

1. 單詞長度固定：由於所有的單詞長度固定，這意味著子串的總長度可以通過簡單的乘法來計算 (總長度 = 單詞數 * 單詞長度)。這也為遍歷提供了便利。

2. 使用滑動窗口：對於每個可能的起始位置（基於單詞長度），我們可以使用滑動窗口來檢查是否有匹配的子串。滑動窗口每次移動一個單詞的長度，這樣可以避免遍歷所有可能的子串。

3. 哈希表進行統計：使用哈希表來存儲 words 中單詞的出現次數，並檢查子串中是否包含相同次數的單詞。

4. 避免重複計算：通過多次遍歷字符串，每次以單詞長度為步長，可以有效減少計算次數。

解題步驟：

1. 初始化：創建一個哈希表 tot 來統計 words 中每個單詞的出現次數。然後計算字符串 s 的長度，單詞的數量 m，以及單詞的長度 w。

2. 滑動窗口：對於每個可能的起始位置 i（從 0 到 w-1），我們進行滑動窗口操作。每次窗口的大小為 m*w，即子串的總長度。

3. 檢查子串：通過哈希表 wd 記錄當前窗口內單詞的出現次數，並且比較這些單詞的次數與 tot 中的對應次數。如果匹配成功，則記錄當前窗口的起始位置。

4. 返回結果：將所有匹配的起始位置添加到結果中並返回。

code

class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        vector<int> ans;
        if (words.empty()) return ans;
        
        unordered_map<string, int> tot;
        for (const auto& word : words) 
            tot[word]++;
        
        int n = s.size(), m = words.size(), w = words[0].size();
        
        // 遍歷每個可能的起始點
        for (int i = 0; i < w; i++) {
            int cnt = 0;
            unordered_map<string, int> wd;
            
            // 滑動窗口
            for (int j = i; j <= n; j += w) {
                // 移出左邊界外的單詞
                if (j >= i + m * w) {
                    string s1 = s.substr(j - m * w, w);
                    wd[s1]--;
                    if (tot[s1] > wd[s1]) cnt--;
                }
                
                // 加入當前單詞
                if (j + w <= n) { // 確保不越界
                    string s2 = s.substr(j, w);
                    wd[s2]++;
                    if (tot[s2] >= wd[s2]) cnt++;
                }
                
                // 當匹配到所有單詞時，記錄位置
                if (cnt == m) 
                    ans.push_back(j - (m - 1) * w);
            }
        }
        
        return ans;
    }
};

時間與空間複雜度

• 時間複雜度：O(N * M)，其中 N 是字符串 s 的長度，M 是單詞數量。每次滑動窗口的操作都是基於單詞的長度進行遍歷，因此時間複雜度與字符串的長度成正比。

• 空間複雜度：O(M * W)，這裡 M 是單詞數量，W 是單詞的長度。存儲哈希表需要額外的空間。